From a terminology perspective, this description is concerned with an underlying continuous signal (also referred to as the source signal) that is sampled, by some process, to produce a sampled signal. Mathematically, the sampled signal is represented by a series of points referred to a coordinate system having an independent variable axis, and a dependent variable axis. The sampled signal is referred to merely as the sampled signal, or as an input sampled signal (if it is to be processed), or as an output sampled signal (if it is output from a process). The disclosed interpolation process is applied to an input sampled signal, which is associated with an underlying continuous signal, to thereby produce a sampled output signal.
In many applications which process a sampled signal, it is required to find the value (of the dependent variable) of the underlying continuous signal at locations (ie at values of the independent variable) for which no sample is available. Interpolation is a process by which the underlying continuous signal can be reconstructed/estimated using the available samples of the sampled signal. Interpolation may also be used to find the value of derivatives of a sampled signal at locations for which no sample is available. In this case the derivative of the underlying continuous signal is estimated using the available samples of the sampled signal.
Interpolation is a fundamental part of many image/video processing applications, such processing including but not being limited to resolution conversion (magnifying and minimizing), warping, rotating, sub-pixel transition and motion estimation.
One conventional interpolation scheme uses a continuous symmetric function (also referred to as a continuous symmetric kernel) such as a piecewise Cubic or Spline, and convolves the input sampled signal with the continuous kernel to reconstruct the original signal. The result of the convolution is calculated at a finite number of output points to produce an output signal that is also a sampled version of the underlying continuous signal. This interpolation process, therefore, finds the value of the underlying signal at a finite number of samples only. For each output sample, a convolution of the kernel, centred at desired point (also referred to as the interpolated sample or the sample to be interpolated or the desired output sample), and the sampled input signal must be calculated.
Interpolation schemes are computationally expensive as the process must be repeated for every output sample. Often this is the main bottleneck in the processing pipeline in question. Calculation of interpolation kernel coefficients (also referred to merely as kernel coefficients or interpolation coefficients, and described in relation to FIG. 1) is typically required for each output sample, and the need for this calculation contributes a significant portion of the typical total computation cost.
One known technique for reducing the cost of kernel calculation involves pre-calculating and storing kernel coefficients in a table. This technique, however, is not suitable for arbitrary rate rescaling as different scaling rates require calculation of the kernel at different points, so a large table is necessary for storing the required kernel coefficients, which involves correspondingly costly pre-calculation.
U.S. Pat. No. 5,930,407 aims to reduce the complexity of Cubic kernel calculation by factorizing the common terms. The complexity of the kernel calculation, however, is still significant.